Discrete Mathematics: The Foundations of Counting

Counting is the art of determining the size of finite sets without the tedious labor of physical enumeration. By leveraging logical structures, we can solve problems ranging from simple menu combinations to complex cryptographic permutations.

The Logic of "OR" and "AND"

Two pillars support the entire field of combinatorics. Their application depends entirely on whether we are viewing a task as a single choice from multiple categories or a sequence of choices.

The Addition Principle (Rule of Sum)

If a set $X$ is partitioned into disjoint subsets $X_1, X_2, \dots, X_n$, then the total number of elements $|X|$ is the sum of the sizes of those subsets:

$$|X| = |X_1| + |X_2| + \dots + |X_n|$$

Analogy: Choosing a meal at Kay’s Quick Lunch by picking either a sandwich from the Main Course menu OR an appetizer from the Appetizer menu. You cannot have both; you choose one item.

The Multiplication Principle (Rule of Product)

If an activity consists of $t$ successive steps, where step $i$ has $n_i$ possible outcomes, the total number of ways to complete the task is the product of the possibilities at each step:

$$N = n_1 \times n_2 \times \dots \times n_t$$

Analogy: Configuring a "Big Pickup" truck. You must choose an engine (5 options) AND a cab style (3 options). The total configurations equal $5 \times 3 = 15$.

Code Implementation and Complexity

In computer science, these principles manifest in loop structures. Sequential loops represent the Addition Principle, while nested loops represent the Multiplication Principle.

// Addition Principle (m + n executions)

for i = 1 to m: println(i)

for j = 1 to n: println(j)

// Multiplication Principle (m * n executions)

for i = 1 to m:

  for j = 1 to n:

    println(i, j)

🎯 Core Principle

Distinguish by keywords: "OR" signifies Addition (mutually exclusive choices), while "AND" or "Successive" signifies Multiplication (independent steps in a sequence).

QUESTION 1

How many dinners at Kay's Quick Lunch (Figure 6.1.1) consist of one appetizer and one beverage, assuming there are 3 appetizers and 4 beverages?

QUESTION 2

In the provided code snippet, how many times are the print statements executed in total? [Code: for i = 1 to m, println(i), for j = 1 to n, println(j)]

m × n

$m + n$

$m^n$

$n^m$

QUESTION 3

How many strings of length 3 can be formed using the letters {A, B, C, D, E} if we allow repetitions?

125

243

QUESTION 4

Using the public key (n=713, e=29), what is the encryption of the message M = 333?

333

557

128

712

QUESTION 5

How many strings of length 3 using the letters {A, B, C, D, E} contain the letter A at least once (repetitions allowed)?

125

Challenge: Advanced Combinatorial Reasoning

Trucks, Triangles, and Pigeonholes

Scenario: Big pickups appeal because of the seemingly infinite ways they can be personalized. A New York Times article suggests you need the math skills of Will Hunting to total the configurations. Let's analyze a model with 5 engine options (3.9L V6, 5.2L V8, 5.9L V8, 5.9L Turbo-diesel, 8L V10).

Define lexicographic order and explain why it is useful in counting structures.

Solution: Lexicographic order is a generalization of the alphabetical order of the words in a dictionary to sequences of ordered symbols. Given two sequences $a_1...a_n$ and $b_1...b_n$, we say $a < b$ if at the first index $i$ where $a_i \neq b_i$, we have $a_i < b_i$. It is useful because it provides a systematic way to list all permutations or combinations without omission or repetition.

What is a permutation of $x_1, \dots, x_n$? Provide a formal definition.

Solution: A permutation of a set of distinct objects is an ordered arrangement of these objects. For a set of $n$ elements, a permutation is a bijection from the set $\{1, 2, \dots, n\}$ to the set itself, where the order of elements in the resulting sequence matters.

Prove that if five cards are chosen from an ordinary 52-card deck, at least two cards are of the same suit.

Solution: This is an application of the Pigeonhole Principle. There are 4 possible suits (the "holes") and 5 cards are chosen (the "pigeons"). Since $5 > 4$, by the Pigeonhole Principle, at least one suit must contain $\lceil 5/4 \rceil = 2$ cards. Thus, at least two cards must share a suit.

In how many ways can we select eight balls from a bag containing red, blue, and yellow balls (at least 8 of each)? (Difficulty: Stem Words: 18, Length: Short)

Solution: This is a combinations with repetition problem. Using the stars and bars formula $C(n+r-1, r)$ where $n=3$ categories and $r=8$ selections: $C(3+8-1, 8) = C(10, 8) = C(10, 2) = (10 \times 9) / 2 = 45$ ways.